§1.1. Field of the Invention
The present invention concerns peer-to-peer (“P2P”) communications. In particular, the present invention concerns reducing or minimizing delays in P2P communications, such as P2P video streaming.
§1.2. Background Information
IP-level multicast has not been widely deployed in the Internet. Recently, multicast functionality has been implemented at the application layer. (See, e.g., the paper Chu, Y., Rao, S., and Zhang, H., “A Case for End System Multicast,” Proceedings of ACM SIGMETRICS (2000); and the paper Francis, P. Yoid, “Extending the Internet Multicast Architecture,” Tech. rep., Cornell University, April 2000 available at http://www.cs.cornell.edu/people/francis/yoidArch.pdf.) For example, users interested in the same video program may form an application layer overlay network for P2P video streaming.
P2P video streaming systems are generally categorized as tree-based and mesh-based. In a tree-based P2P video streaming system, peers form an application layer multicast tree. Video data flows from a source server to a peer through multiple hops in the tree. The video delay perceived by a peer includes video transmission delays and propagation delays on all hops. The fan out degree of a peer in the tree is determined by the number of simultaneous video streams that can be supported by a peer's uploading capacity. An example of a tree-based P2P video streaming system is Overcast. (See, e.g., the article Jannotti, J., Gifford, D. K., Johnson, K. L., Kaashoek, M. F., AND O'Toole, JR., J. W., “Overcast: Reliable Multicasting with an Overlay Network,” Proceedings of Operating Systems Design and Implementation, pp. 197-212 (2000).)
Unfortunately, present tree-based P2P video streaming systems have some problems. More specifically, since a typical peer can only upload a small number of concurrent video streams, the multicast tree formed by peers tends to have a narrow width, and consequently, a large depth. Unfortunately, with such a large depth multicast tree, peers at low layers of the multicast tree can experience excessive delays between the time of video request to the receipt of the video stream. For cases in which each peer has only enough capacity to upload one stream to one other peer, the multicast tree topology formed by N peers becomes a chain with N hops. In this worst case scenario, the multicast tree is a chain (has a width of one and a depth of N), and the delay for the peer at the end of the chain is the aggregate video chunk transmission and propagation delays along the N hops.
To address the foregoing problem, multi-tree based P2P video streaming approaches have been proposed. (See, e.g., the papers: Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A., and Singh, A., “SplitStream: High-bandwidth Multicast in Cooperative Environments,” Proceedings of ACM Symposium on Operating Systems Principles (SOSP) (2003); and Kostic, D., Rodriguez, A., Albrecht, J., and Vahdat, A., “Bullet: High Bandwidth Data Dissemination using an Overlay Mesh,” Proceedings of ACM Symposium on Operating Systems Principles (SOSP) (2003).) In multi-tree streaming, the server divides the stream into m sub-streams. Instead of one streaming tree, m sub-trees are formed—one for each sub-stream. When a fully balanced multi-tree is used for streaming, the node degree of each sub-tree is m. Each peer joins all sub-trees to retrieve sub-streams. Any peer is positioned on an internal node in only one sub-tree and only uploads one sub-stream to its m children peers in that sub-tree. In each of the remaining (m−1) sub-trees, the peer is positioned on a leaf node and downloads a sub-stream from its parent peer. It has been shown that if all peers have the same uploading capacity and the propagation delays among peers are dominated by video chunk transmission delays, the average and worst-case delays for peers in a m-degree multi-tree streaming systems are m logm N times the video chunk transmission delay from one peer to another peer. The shortest streaming delay is achieved when the degree m=3, and shortest achievable delay is 1.89 log2 N times the chunk transmission delay.
Many recent P2P streaming systems adopt mesh-based streaming approach. (See, e.g., the articles: Zhang, X., Liu, J., Li, B., And Yum, T-S. P., “DONet/CoolStreaming: A Data-Driven Overlay Network for Peer-to-Peer Live Media Streaming,” Proceedings of IEEE INFOCOM (March 2005); Pai, V., Kumar, K., Tamilmani, K., Sambamurthy, V., And Mohr, A., “Chainsaw: Eliminating Trees from Overlay Multicast,” The Fourth International Workshop on Peer-to-Peer Systems (2005); Zhang, M., Zhao, L., Tang, J. L. Y., And Yang, S., “A Peer-to-Peer Network for streaming Multicast through the Internet,” Proceedings of ACM Multimedia (2005); and Magharei, N., And Rejaie, R., “Prime: Peer-to-Peer Receiver-Driven Mesh-Based Streaming,” Proceedings of IEEE INFOCOM (2007).) In some of these mesh-based systems, there is no static streaming topology. Rather, peers establish and terminate peering relationships dynamically. Further, a peer may download video from and/or upload video to multiple peers simultaneously. Unfortunately, the video data flows among peers are largely uncoordinated. Consequently, the delay performance of existing mesh-based streaming systems is unsatisfactory.
In view of the foregoing limitations of existing P2P video streaming techniques, it would be useful to have improved P2P video streaming methods and systems. For example, it would be useful to have P2P video streaming methods and systems in which peers experience lower streaming delays.